package recursive.KthGrammar;
/**
 * @Date 2020/03/30
 * @author 王光浩
 * @Thinking 使用递归实现
 * @Analysis 时间复杂度O（2^n)，空间复杂度O（N）,错误方法，原因：错误理解题目意思，但是这种思路值的保留
 */
public class MyMethodOne {
	public int kthGrammar(int N, int K) {
		int count=(int)Math.pow(2,N-2);
		return (recursive(N)<<(32-count-K-1))<0?1:0;
    }
	//获取第N层的数字
	private int recursive(int N) {
		if(N==1)return 0;
		int ret=recursive(N-1);         //获取上一层的值
		int count=(int)Math.pow(2,N-2); //统计上一层元素的个数
		int help=ret<<(32-count);
		for(int i=0;i<count;i++) {
			ret<<=1;
			if(help<0)ret+=1;
			help<<=1;
		}
		return ret;
	}
}
